343. 整数拆分

为保证权益，题目请参考 343. 整数拆分(From LeetCode).

解决方案1

CPP

//
// Created by lenovo on 2020-07-30.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * @brief 函数
 */
class Solution {
public:
    static int integerBreak(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
};

int main() {
    return 0;
}

Python

# 343. 整数拆分
# https://leetcode-cn.com/problems/integer-break/


class Solution:
    def integerBreak(self, n: int) -> int:
        a, b = divmod(n, 3)
        if b == 0:
            if a == 1:
                return 2
            else:
                b = 1
        elif b == 1:
            a -= 1
            b = 2 * 2
        elif b == 2:
            if a == 0:
                return 1
        return (3 ** a) * b